package com.example.demo.leetcode.codetop.bytedance;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 *
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 *
 *  
 *
 * 示例 1：
 * 输入：head = [1,2,3,4]
 * 输出：[1,4,2,3]
 * 示例 2：
 *    1 -> 2 -> 3 -> 4 -> null
 *    p  pnext  q   qnext
 *
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reorder-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/25 16:37
 */
public class 重排链表 {

   public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }

    /**
     * @Desciption: 普通解法
     * @param head:
     */
    public void reorderList(ListNode head) {

       if(head.next == null){
           return;
       }
       ListNode p = head;
       ListNode q = head;

       while(q.next.next != null){
           q = q.next;
       }
       while(p != q){

           ListNode pnext = p.next;
           ListNode qnext = q.next;

           qnext.next = pnext;
           q.next = null;
           p.next = qnext;

           //p后移两位
           p = p.next.next;
           //重新寻找最后一个节点
           q = p;
           while(q!= null && q.next!= null && q.next.next != null){
               q = q.next;
           }
       }
    }

    /**
     * @Desciption:
     *  方法二:
     * 1.找出链表的中间点(快慢指针)
     * 2.找出中间点后 将中间点后的链表逆序
     * 3.逆序后后重新合并两个链表
     *
     *  1->2->3->4->5->6->null
     *
     *  1->2->3->null
     *
     *  4->5->6->null
     *
     *
     *  1->    2->  3->null
     *  head1  next
     *         head1
     *  6->    5->  4->null
     * head2
     *         head2
     * @param head:
     */
    public void reorderList2(ListNode head) {

        ListNode middleNode = middleNode(head);

        ListNode secondNode = reverse(middleNode);

        //合并
         merge(head,secondNode);
    }


    public ListNode merge(ListNode head1,ListNode head2){


        ListNode res = new ListNode(0);
        ListNode head = res;
        int count = 1;

        while(head1!=null && head2!=null){
            if((count & 1)==1){
                head.next = head1;
                head1 = head1.next;
                head = head.next;
            }else{
                head.next = head2;
                head2 = head2.next;
                head = head.next;

            }
            count++;
        }

        while(head1 != null){
            head.next = head1;
            head1 = head1.next;
            head = head.next;
        }

        while(head2 != null){
            head.next = head2;
            head2 = head2.next;
            head = head.next;
        }

        return res.next;
    }


    public ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head!=null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    public ListNode middleNode(ListNode head){
       ListNode slow = head;
       ListNode fast = head;
       while(fast!=null && fast.next!=null && fast.next.next!=null){
           slow = slow.next;
           fast = fast.next.next;
       }
       ListNode middle = slow.next;
       slow.next = null;
       return middle;
    }
}
